package cn.edu.xjtu.competiton.力扣.周赛.weekly291;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author Hydrion-QLz
 * @date 2022-05-01 11:05
 * @description https://leetcode-cn.com/contest/weekly-contest-291/problems/total-appeal-of-a-string/
 * <p>
 * 字符串的 引力 定义为：字符串中 不同 字符的数量。
 * <p>
 * 例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。
 * 给你一个字符串 s ，返回 其所有子字符串的总引力 。
 * <p>
 * 子字符串 定义为：字符串中的一个连续字符序列。
 */
public class forth {
    public static void main(String[] args) {
        forth solution = new forth();
        int[] arr = {};
        System.out.println(solution.appealSum("abbca"));
    }

    public long appealSum(String s) {
        char[] arr1 = s.toCharArray();
        int[] arr2 = new int[26];
        long count = 0;
        int index;
        long len = arr1.length;
        Arrays.fill(arr2, -1);
        for (int i = 0; i < arr1.length; i++) {
            index = arr1[i] - 'a';
            count += (len - i) * (i - arr2[index]);
            arr2[index] = i;
        }
        return count;
    }

    public long appealSum1(String s) {
        int n = s.length();
        node[][] dp = new node[n][n];
        long ans = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = new node();
            dp[i][i].val = 1;
            Set<Character> set = new HashSet<>();
            set.add(s.charAt(i));
            dp[i][i].set = set;
            ans++;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = new node();
                if (dp[i][j - 1].set.contains(s.charAt(j))) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j].val = dp[i][j - 1].val + 1;
                    dp[i][j].set = dp[i][j - 1].set;
                    dp[i][j].set.add(s.charAt(j));
                }
                ans += dp[i][j].val;
            }
            dp[i][i].set.clear();
        }
        return ans;
    }

    public long appealSum2(String s) {
        int n = s.length();
        node[] dp = new node[n];
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    dp[j] = new node();
                    dp[j].val = 1;
                    dp[j].set = new HashSet<>();
                    dp[j].set.add(s.charAt(j));
                    ans++;
                } else {
                    dp[j] = new node();
                    if (dp[j - 1].set.contains(s.charAt(j))) {
                        dp[j] = dp[j - 1];
                    } else {
                        dp[j].val = dp[j - 1].val + 1;
                        dp[j].set = dp[j - 1].set;
                        dp[j].set.add(s.charAt(j));
                    }
                    ans += dp[j].val;
                }
            }
        }
        return ans;
    }
}

class node {
    int val;
    Set<Character> set;
}